00. Linear Algebra Basics

Learning Objectives

After this lecture, you will be able to:

• Analyze Fundamental Subspaces: Identify and compute the dimensions of the four fundamental subspaces of a matrix ($\mathcal{R}(A), \mathcal{N}(A), \mathcal{R}(A^\top), \mathcal{N}(A^\top)$) using the Rank-Nullity Theorem.
• Manipulate Norms and Inner Products: Apply standard and generalized inner products, vector norms ($\ell_1, \ell_2, \ell_\infty$), and their duals to establish inequalities like Cauchy-Schwarz and Hölder.
• Perform Geometric Operations: Construct orthonormal bases via Gram-Schmidt and compute orthogonal projections onto subspaces and affine sets.
• Characterize PSD Matrices: Determine positive semidefiniteness using eigenvalues, variational forms ($x^\top Ax \ge 0$), and the Schur Complement lemma.
• Solve Least Squares: Derive and solve the normal equations for overdetermined systems and interpret the solution geometrically as an orthogonal projection.
• Apply Matrix Calculus: Compute gradients and Hessians for linear, quadratic, and log-determinant functions, which are essential for first- and second-order optimization algorithms.

1. Mathematical Atoms: Sets, Functions, and Combinations

1.1 The Geometric "Atoms" of Optimization

In convex optimization, we view algebraic problems through a geometric lens. Throughout this course, you will repeatedly perform three fundamental operations. Recognizing these "atoms" allows you to parse complex problems into simple, manageable geometric components:

1. Mixing (Convex Combinations): Optimization often involves "averaging" or interpolating between candidate solutions.
   Example: In a portfolio optimization problem, if you have two valid asset allocations, any weighted average of them is also a valid allocation. This operation of "mixing" defines the geometry of convex sets.
2. Measuring (Norms & Inner Products): We need precise tools to quantify "error" and "similarity".
   Example: The objective function often measures the size of the residual vector (how far is our prediction from the data?). Norms act as rulers to measure these lengths, while inner products act as protractors to measure angles (e.g., is the gradient pointing towards the optimum?).
3. Pullback (Preimages): Constraints are typically defined by functions, such as $g(x) \le 0$. This defines a set implicitly: the set of all $x$ that map to non-positive values.
   Example: Understanding constraints as preimages ($g^{-1}((-\infty, 0])$) allows us to deduce the shape of the feasible region directly from the properties of the function $g$.

Understanding these three operations transforms optimization from abstract symbol manipulation into concrete geometric reasoning.

1.2 Scalars, Vectors, and Matrices

• Scalars: Real numbers $a \in \mathbb{R}$.
• Vectors: A vector $x \in \mathbb{R}^n$ is formally a function $\{1,\dots,n\} \to \mathbb{R}$. We represent it as an ordered $n$-tuple (column vector).
  Equality: $x = y \iff x_i = y_i$ for all $i$.
• Matrices: $A \in \mathbb{R}^{m \times n}$.
  Matrix-Vector Product: The definition $(Ax)_i = \sum_{j=1}^n A_{ij} x_j$ is chosen specifically to enforce linearity: $A(\alpha x + \beta y) = \alpha Ax + \beta Ay$.
  Column View: $Ax = \sum_{j=1}^n x_j A_{:j}$. $Ax$ is a linear combination of the columns of $A$. This is the "synthesis" view: $A$ builds a new vector from its columns.
  Row View: $(Ax)_i = A_{i:}^\top x$. The $i$-th entry is the dot product of the $i$-th row with $x$. This is the "analysis" view: each row "measures" the input vector $x$.

1.3 Preliminaries: Lines and Line Segments

We work in the vector space $\mathbb{R}^n$ equipped with the standard inner product $\langle x, y \rangle = x^\top y = \sum_{i=1}^n x_i y_i$ and the induced Euclidean norm $\|x\|_2 = \sqrt{\langle x, x \rangle}$. Geometric objects like lines and segments are the building blocks of convexity.

Line through two points

Given two distinct points $x_1, x_2 \in \mathbb{R}^n$, the line passing through them is the set of all affine combinations of these points:

As $\theta$ varies over $\mathbb{R}$, $y$ traces out the infinite line passing through $x_2$ in the direction of $x_1 - x_2$. The value $\theta=0$ corresponds to $x_2$, and $\theta=1$ corresponds to $x_1$.

Line segment between two points

The line segment connecting $x_1$ and $x_2$, denoted $[x_1, x_2]$, corresponds to restricting the parameter $\theta$ to the unit interval $[0, 1]$:

This parametrization is the definition of a convex combination of two points. Intuitively, a convex combination is a "weighted average" that lies physically between the points. If you imagine a mass at $x_1$ and a mass at $x_2$, the point $y$ is the center of mass when the weights are $\theta$ and $1-\theta$. A set is defined to be convex if and only if it contains the entire line segment between any pair of its points.

1.4 Functions and Preimages

A function $f: \mathcal{X} \to \mathcal{Y}$ maps domain $\mathcal{X}$ to codomain $\mathcal{Y}$. The range (or image) is the set of actual outputs: $\mathrm{range}(f) = \{f(x) : x \in \mathcal{X}\} \subseteq \mathcal{Y}$.

The Preimage Laws

For a set $B \subseteq \mathcal{Y}$, the preimage is $f^{-1}(B) = \{x \in \mathcal{X} : f(x) \in B\}$. This exists even if $f$ is not invertible. Preimages respect all set operations perfectly:

Why this matters: Constraints like $g(x) \le 0$ define the set $g^{-1}((-\infty, 0])$. If $g$ is convex, the preimage of the convex set $(-\infty, 0]$ is convex.

1.5 Combinations and Hulls

Different rules for "mixing" vectors generate different geometric objects.

Translation Invariance of Affine Combinations

Affine combinations are "origin-independent". If $y = \sum \theta_i x_i$ with $\sum \theta_i = 1$, then shifting all points by $v$ shifts the result by $v$:

The 2-Point Convex Hull is a Segment

The set of convex combinations of $x$ and $y$ is $S = \{\theta x + (1-\theta)y : \theta \in [0, 1]\}$.
This matches the geometric definition of the segment $[x, y]$: start at $y$, move towards $x$ by fraction $\theta$. $$ \theta x + (1-\theta)y = y + \theta(x-y) $$ A set is convex if it contains the line segment between any pair of its points.

2. Subspaces and the Four Fundamental Spaces

A linear subspace is a set of vectors that is closed under addition and scalar multiplication. Given a matrix $A \in \mathbb{R}^{m \times n}$, we can define four fundamental subspaces that characterize the behavior of the linear map $T(x) = Ax$.

• Column Space (Range): $\mathcal{R}(A) = \{Ax \mid x \in \mathbb{R}^n\} \subseteq \mathbb{R}^m$. This is the set of all possible outputs of the linear map, i.e., the span of the columns of $A$.
• Nullspace (Kernel): $\mathcal{N}(A) = \{x \in \mathbb{R}^n \mid Ax = 0\}$. This is the set of all input vectors that are mapped to the zero vector.
• Row Space: $\mathcal{R}(A^\top) \subseteq \mathbb{R}^n$. This is the span of the rows of $A$.
• Left Nullspace: $\mathcal{N}(A^\top) = \{y \in \mathbb{R}^m \mid A^\top y = 0\}$. This is the nullspace of the transpose of $A$.
  Why do we care? The Left Nullspace defines the constraints on solvability. The system $Ax=b$ has a solution if and only if $b$ is orthogonal to every vector in the Left Nullspace ($b \perp \mathcal{N}(A^\top)$). This is the Fredholm Alternative.

These subspaces are linked by the Fundamental Theorem of Linear Algebra. This theorem is not just an algebraic curiosity; it is the geometric foundation for understanding when linear systems are solvable (feasibility) and when they are unique.

• Relationship 1: $\mathcal{R}(A) \perp \mathcal{N}(A^\top)$ in $\mathbb{R}^m$. The range is the orthogonal complement of the left nullspace.
• Relationship 2: $\mathcal{R}(A^\top) \perp \mathcal{N}(A)$ in $\mathbb{R}^n$. The row space is the orthogonal complement of the nullspace.

The Fredholm Alternative (Theorem of Alternatives)

A crucial consequence of the orthogonality $\mathcal{R}(A) = \mathcal{N}(A^\top)^\perp$ is a solvability criterion for linear systems, known as the Fredholm Alternative. For any $A \in \mathbb{R}^{m \times n}$ and $b \in \mathbb{R}^m$, exactly one of the following two statements is true:

1. Primal Feasibility: The system $Ax = b$ has a solution.
2. Dual Certificate of Infeasibility: There exists a vector $y$ such that $A^\top y = 0$ but $b^\top y \neq 0$.

Interpretation: If $Ax=b$ has no solution, then $b$ does not lie in $\mathcal{R}(A)$. Since $\mathcal{R}(A)^\perp = \mathcal{N}(A^\top)$, there must be a component of $b$ that lies in $\mathcal{N}(A^\top)$. This component $y$ serves as a witness (or certificate) that proving $b$ is unreachable by $A$. This logic generalizes to Farkas' Lemma and strong duality in later lectures.

Rank and Rank–Nullity Theorem

$\mathrm{rank}(A) = \dim \mathcal{R}(A)$. For $A \in \mathbb{R}^{m \times n}$: $$ \dim \mathcal{N}(A) + \mathrm{rank}(A) = n $$ This fundamental result relates the dimensions of the domain's subspaces to the rank of the mapping.

3. Algebraic Invariants: Determinant, Trace, and Eigenvalues

While a matrix $A$ represents a linear map in a specific basis, we are often interested in properties that are intrinsic to the map itself, independent of the basis. These are called invariants.

3.1 The "Big Three" Invariants

For a square matrix $A \in \mathbb{R}^{n \times n}$ with eigenvalues $\lambda_1, \dots, \lambda_n$ (counted with algebraic multiplicity):

• Trace: $\mathrm{tr}(A) = \sum_{i=1}^n A_{ii} = \sum_{i=1}^n \lambda_i$.
• Determinant: $\det(A) = \prod_{i=1}^n \lambda_i$.
• Eigenvalues: Roots of the characteristic polynomial $p_A(\lambda) = \det(A - \lambda I)$.

3.2 The "Isotropic Scaling" Lemma

While eigenvalues describe the behavior of $A$ along specific directions, sometimes the matrix acts uniformly in all directions. A classic result connects this geometric isotropy to the algebraic structure of the matrix. We ask: what if every vector is an eigenvector?

Geometric Intuition: A general symmetric matrix maps the unit sphere to an ellipsoid. The eigenvectors correspond to the axes of the ellipsoid. If every vector is an eigenvector, then every direction is a principal axis. The only ellipsoid with this symmetry is a sphere (isotropic scaling).

3.3 Algebraic Properties

Linearity of Trace

The trace is a linear functional: $$ \mathrm{tr}(A + B) = \mathrm{tr}(A) + \mathrm{tr}(B) \quad \text{and} \quad \mathrm{tr}(cA) = c\,\mathrm{tr}(A). $$

Multiplicativity of Determinant

The determinant is multiplicative: $$ \det(AB) = \det(A)\det(B). $$ This reflects the geometric fact that the volume scaling of a composite map is the product of the individual scalings. Note that $\det(AB) = \det(BA)$ even if $AB \neq BA$.

Trace of a Product (Cyclic Property)

In general, $\mathrm{tr}(AB) \neq \mathrm{tr}(A)\mathrm{tr}(B)$. However, the trace is cyclic: $$ \mathrm{tr}(AB) = \mathrm{tr}(BA). $$ More generally, $\mathrm{tr}(ABC) = \mathrm{tr}(BCA) = \mathrm{tr}(CAB)$. This property is crucial for deriving matrix gradients.

3.4 Similarity and Basis Independence

Two matrices $A$ and $B$ are similar if $B = P A P^{-1}$ for some invertible $P$. This represents the same linear operator in a different basis. The detailed mechanics of this coordinate transformation and its connection to diagonalization are covered in depth in Lecture 01.

3.5 Spectral Shift

Adding a multiple of the identity shifts the eigenvalues but preserves eigenvectors. If $Ax = \lambda x$, then: $$ (A + tI)x = Ax + tIx = (\lambda + t)x. $$ Thus, the eigenvalues of $A+tI$ are $\{\lambda_i + t\}$.
Warning: In general, $\det(A+B) \neq \det(A) + \det(B)$. For example, $\det(I+I) = 2^n \neq 1+1$.

4. Inner Products, Norms, and Angles

Inner Products

An inner product on $\mathbb{R}^n$ is a function $\langle \cdot, \cdot \rangle: \mathbb{R}^n \times \mathbb{R}^n \to \mathbb{R}$ satisfying three axioms for all $x, y, z$ and scalars $\alpha, \beta$:

1. Linearity: $\langle \alpha x + \beta z, y \rangle = \alpha\langle x, y \rangle + \beta\langle z, y \rangle$.
2. Symmetry: $\langle x, y \rangle = \langle y, x \rangle$.
3. Positive Definiteness: $\langle x, x \rangle \ge 0$, and $\langle x, x \rangle = 0 \iff x = 0$.

These axioms ensure that "lengths" and "angles" behave as expected. The standard (Euclidean) inner product is defined as $\langle x, y \rangle = x^\top y = \sum_{i=1}^n x_i y_i$.

Weighted Inner Products

For any symmetric positive definite matrix $P \in \mathbb{S}^n_{++}$, we can define a weighted inner product: $$ \langle x, y \rangle_P := x^\top P y $$ This induces the P-norm $\|x\|_P = \sqrt{x^\top P x}$, which measures distance in a skewed coordinate system (related to ellipsoids).

Norms and Convexity

A norm is a function $\|\cdot\|: \mathbb{R}^n \to \mathbb{R}$ assigning a length to each vector. Axioms:

1. Definiteness: $\|x\| \ge 0$, and $\|x\| = 0 \iff x=0$.
2. Homogeneity: $\|\alpha x\| = |\alpha| \|x\|$.
3. Triangle Inequality: $\|x+y\| \le \|x\| + \|y\|$.

The $\ell_1$ and $\ell_\infty$ Norms (Rigorous Proofs)

• $\ell_1$ (Manhattan): $\|x\|_1 = \sum_{i=1}^n |x_i|$.
• $\ell_\infty$ (Chebyshev): $\|x\|_\infty = \max_{i} |x_i|$.

Unit Balls are Convex

A crucial geometric property: The unit ball $B = \{x : \|x\| \le 1\}$ of any norm is a convex set.

The Euclidean Geometry ($\ell_2$)

The Euclidean norm $\|x\|_2 = \sqrt{x^\top x}$ is special because it arises from an inner product.

Foundational Scalar Lemmas

1. 1D Triangle Inequality: $|a+b| \le |a| + |b|$.
   Proof: Squaring both sides (non-negative) gives $(a+b)^2 \le (|a|+|b|)^2 \iff a^2+2ab+b^2 \le a^2+2|a||b|+b^2 \iff ab \le |ab|$, which is always true.
2. Quadratic Non-negativity: If $q(t) = at^2 + bt + c \ge 0$ for all $t$ (with $a > 0$), then the discriminant $b^2 - 4ac \le 0$.
   Reason: If the discriminant were positive, the quadratic would have two real roots and dip below zero between them.

Dual Norms and Polar Sets

The dual norm provides a variational definition of size. For any norm $\|\cdot\|$, its dual $\|\cdot\|_*$ is: $$ \|y\|_* = \sup_{\|x\| \le 1} x^\top y $$ This measures the maximum "correlation" $y$ can have with any unit vector.

Generalized Hölder's Inequality

From the definition, we immediately get the fundamental inequality: $$ x^\top y \le \|x\| \|y\|_* $$ Proof: If $x=0$, trivial. If $x \neq 0$, let $u = x/\|x\|$. Then $\|u\|=1$, so $u^\top y \le \|y\|_* \implies (x/\|x\|)^\top y \le \|y\|_* \implies x^\top y \le \|x\| \|y\|_*$.

Canonical Dual Pairs

• $\ell_2$ is self-dual: $\|y\|_{2,*} = \|y\|_2$. (Aligned by $x = y/\|y\|_2$).
• $\ell_1$ dual is $\ell_\infty$: $\|y\|_{1,*} = \|y\|_\infty$. (Maximize $x^\top y$ on diamond $\to$ pick corner).
• $\ell_\infty$ dual is $\ell_1$: $\|y\|_{\infty,*} = \|y\|_1$. (Maximize $x^\top y$ on box $\to$ match signs).

Polar Sets

The polar of a convex set $C$ is $C^\circ = \{y : y^\top x \le 1 \ \forall x \in C\}$.
For a unit ball $B = \{x : \|x\| \le 1\}$, the polar is exactly the dual unit ball: $$ B^\circ = \{y : \|y\|_* \le 1\} $$ This geometric duality underpins the duality of optimization problems.

Spectral Norm and Convexity

Induced Matrix Norms

The spectral norm is a specific instance of an induced norm (or operator norm). For any vector norms $\|\cdot\|_a$ on the domain and $\|\cdot\|_b$ on the codomain, the induced norm of a matrix $X$ is: $$ \|X\|_{a,b} = \sup_{v \neq 0} \frac{\|Xv\|_b}{\|v\|_a} = \sup_{\|v\|_a = 1} \|Xv\|_b $$ This measures the maximum amplification of the $b$-norm of the output relative to the $a$-norm of the input.

Common Operator Norms

When the domain and codomain are equipped with the same $\ell_p$ norm ($a=b=p$), we write $\|X\|_p$.

• Spectral Norm ($p=2$): $\|X\|_2 = \sigma_{\max}(X)$. (Max stretch of Euclidean length).
• Max Column Sum Norm ($p=1$): The operator norm induced by the $\ell_1$ norm is the maximum absolute column sum. $$ \|X\|_1 = \max_{j} \sum_{i} |X_{ij}| $$ Intuition: The unit ball of $\ell_1$ is a diamond with vertices at $e_j$. The maximum stretch occurs at one of these vertices $X e_j$ (the $j$-th column).
• Max Row Sum Norm ($p=\infty$): The operator norm induced by the $\ell_\infty$ norm is the maximum absolute row sum. $$ \|X\|_\infty = \max_{i} \sum_{j} |X_{ij}| $$ Intuition: This is the dual of the 1-norm case.

Convexity: All induced norms are convex functions of the matrix $X$. This follows because $\|X\|_{a,b} = \sup_{\|u\|_{b^*} \le 1, \|v\|_a \le 1} u^\top X v$, which is a pointwise supremum of linear functions.

Spectral Norm Details

The spectral norm (or operator norm) of a matrix $X \in \mathbb{R}^{m \times n}$ is induced by the Euclidean vector norm: $$ \|X\|_2 = \sup_{v \neq 0} \frac{\|Xv\|_2}{\|v\|_2} = \sup_{\|v\|_2=1} \|Xv\|_2 $$

Intuition: Worst-Case Stretch. The operator norm measures the maximum factor by which the matrix $X$ can "stretch" a vector. It corresponds to the "Lipschitz constant" of the linear map. Geometrically, it is the length of the longest semi-axis of the ellipsoid formed by mapping the unit sphere.

Dual Representation (Crucial for Convexity Proofs): Similar to the max eigenvalue, the spectral norm can be written as a supremum: $$ \|X\|_2 = \sup_{\|u\|_2=1, \|v\|_2=1} u^\top X v $$ Since $f(X) = u^\top X v$ is a linear function of $X$, and $\|X\|_2$ is the supremum of these linear functions, $\|X\|_2$ is a convex function.

Matrix Inner Product and Frobenius Norm

For matrices $X, Y \in \mathbb{R}^{m \times n}$, the trace inner product (also called the Hilbert-Schmidt inner product) is: $$ \langle X, Y \rangle = \mathrm{tr}(X^\top Y) = \sum_{i=1}^m \sum_{j=1}^n X_{ij} Y_{ij} $$ The Frobenius norm (or Hilbert-Schmidt norm) is $\|X\|_F = \sqrt{\langle X, X \rangle}$.

Submultiplicativity of the Frobenius Norm

For compatible matrices $A, B$, we have the inequality $\|AB\|_F \le \|A\|_F \|B\|_F$. This property is crucial for analyzing the convergence of matrix iterations.

5. Orthogonality and Orthonormal Bases

Orthonormal Sets

A set of vectors $q_1, \dots, q_k$ is orthonormal if its elements are mutually orthogonal and each has a norm of 1. Formally, $q_i^\top q_j = \delta_{ij}$, where $\delta_{ij}$ is the Kronecker delta (1 if $i=j$, 0 otherwise). A square matrix $Q$ with orthonormal columns is an orthogonal matrix, satisfying the important property $Q^\top Q = I$, which means $Q^{-1} = Q^\top$. Orthonormal bases are computationally desirable because they are numerically stable and simplify many calculations, such as projections.

Angle Preservation and Orthogonal Matrices

A linear map $A$ preserves angles if $\frac{\langle Ax, Ay \rangle}{\|Ax\|\|Ay\|} = \frac{\langle x, y \rangle}{\|x\|\|y\|}$ for all $x, y$. A stronger condition is that $A$ preserves inner products: $\langle Ax, Ay \rangle = \langle x, y \rangle$.
Using the adjoint property, $\langle x, A^\top A y \rangle = \langle x, y \rangle$ for all $x, y$, which implies $A^\top A = I$. Thus, matrices that preserve geometry (lengths and angles) are exactly the orthogonal matrices (possibly scaled).

The Gram-Schmidt Process

The Gram-Schmidt process is an algorithm for constructing an orthonormal basis from a set of linearly independent vectors. Starting with a vector, it iteratively subtracts the components that lie in the direction of the previously processed vectors, leaving a new, orthogonal vector that is then normalized. $$ \tilde{q}_k = a_k - \sum_{i=1}^{k-1} (q_i^\top a_k) q_i, \quad q_k = \frac{\tilde{q}_k}{\|\tilde{q}_k\|_2} $$

The QR Decomposition

The QR decomposition expresses a matrix $A$ as the product of an orthonormal matrix $Q$ and an upper triangular matrix $R$. This decomposition is a direct outcome of the Gram-Schmidt process and is fundamental to numerical linear algebra. For a matrix $A \in \mathbb{R}^{m \times n}$ with full column rank, we can write $A = QR$, where $Q \in \mathbb{R}^{m \times n}$ has orthonormal columns and $R \in \mathbb{R}^{n \times n}$ is upper-triangular.
Applications:

• Solving Linear Systems: The system $Ax=b$ becomes $QRx=b$, which simplifies to $Rx = Q^\top b$. This is easily solved using back substitution and is far more numerically stable than forming the normal equations.
• Projections: The projection onto the column space of $A$ is given by $P = QQ^\top$.

6. Positive Semidefinite Matrices

6.1 The Space of Symmetric Matrices ($\mathbb{S}^n$)

In convex optimization, a central object is the Hessian matrix $\nabla^2 f(x)$. By Schwarz's Theorem, if a function is twice continuously differentiable, its Hessian is symmetric. A matrix $A \in \mathbb{R}^{n \times n}$ is symmetric if $A = A^\top$. The set of such matrices is denoted $\mathbb{S}^n$.

The Spectral Theorem

If $A \in \mathbb{S}^n$, then:

1. All eigenvalues ($\lambda_1, \dots, \lambda_n$) are real numbers.
2. There exists a set of orthonormal eigenvectors $q_1, \dots, q_n$.
3. $A$ can be diagonalized as $A = Q \Lambda Q^\top$, where $Q$ is an orthogonal matrix ($Q^\top Q = I$) containing the eigenvectors, and $\Lambda$ is a diagonal matrix containing the eigenvalues.

Why are Eigenvectors of Symmetric Matrices Orthogonal?

The Spectral Theorem guarantees orthogonal eigenvectors for symmetric matrices. The proof relies on the adjoint property.

Implication for convexity: The "shape" of a multivariable function (bowl vs. saddle) is entirely determined by the signs of the eigenvalues of its Hessian.

6.2 Positive Semidefinite (PSD) Matrices

This definition is central to the course. It provides the matrix equivalent of a "non-negative number" and underpins the definition of Convex Functions (Lecture 05) and Semidefinite Programming (Lecture 08).

Definition A: The Variational Definition

A symmetric matrix $A \in \mathbb{S}^n$ is Positive Semidefinite (PSD), denoted as $A \succeq 0$, if:

Geometric Intuition (Generalized Non-Negative Numbers): Just as a non-negative number $a \ge 0$ allows us to define convex quadratic functions like $f(x) = ax^2$, a PSD matrix allows us to define convex quadratic forms in higher dimensions. If $A \succeq 0$, the function $f(x) = x^\top A x$ looks like a bowl. If $A$ has a negative eigenvalue, the function looks like a saddle (curves down in some directions), breaking convexity.

Curvature: If $A$ is the Hessian $\nabla^2 f(x)$, the term $x^\top A x$ is the second derivative along the line defined by vector $x$. $A \succeq 0$ means the function has non-negative curvature in every possible direction.

Definition B: The Eigenvalue Definition

A symmetric matrix $A \in \mathbb{S}^n$ is PSD if and only if all its eigenvalues are non-negative:

Factorization of PSD Matrices (Gram Matrix)

A symmetric matrix $A$ is PSD if and only if it can be written as a Gram matrix: $A = B^\top B$ for some matrix $B$ (not necessarily square).
Proof: If $A \succeq 0$, spectral decomposition gives $A = Q \Lambda Q^\top = (Q \Lambda^{1/2}) (Q \Lambda^{1/2})^\top$. Let $B = (Q \Lambda^{1/2})^\top$. This $B$ is a "square root" of $A$. Conversely, if $A = B^\top B$, then $x^\top A x = x^\top B^\top B x = (Bx)^\top (Bx) = \|Bx\|_2^2 \ge 0$.

6.3 Geometry of PSD Matrices: Ellipsoids

Positive Definite (PD) matrices define the shape of ellipsoids. For a matrix $P \in \mathbb{S}^n_{++}$, the set: $$ \mathcal{E} = \{ x \in \mathbb{R}^n \mid x^\top P x \le 1 \} $$ is an ellipsoid centered at the origin.

• Axes alignment: The axes of the ellipsoid are aligned with the eigenvectors of $P$.
• Axis lengths: The semi-axis lengths are $1/\sqrt{\lambda_i}$, where $\lambda_i$ are the eigenvalues of $P$. Note the inverse relationship: a large eigenvalue means steep curvature in the quadratic bowl, which corresponds to a short axis in the level set ellipsoid (the function rises quickly).

This geometric link explains why "conditioning" matters. If the ratio $\lambda_{\max}/\lambda_{\min}$ is large, the ellipsoid is very long and thin (a deep valley in one direction, flat in another), making optimization difficult.

6.4 The Rayleigh Quotient and Eigenvalues

The maximum eigenvalue $\lambda_{\max}(A)$ can be defined as an optimization problem:

This is the Rayleigh Quotient. This definition proves that $\lambda_{\max}(A)$ is a convex function of $A$. Notice that for a fixed $x$, the function $g(A) = x^\top A x$ is linear in $A$. Since $\lambda_{\max}(A)$ is the pointwise supremum of a family of linear functions (indexed by $x$), it is a convex function.

6.5 The Schur Complement Lemma

A powerful tool for handling block matrices in optimization is the Schur Complement. It allows us to convert complicated nonlinear constraints into Linear Matrix Inequalities (LMIs) and provides a systematic way to check positive semidefiniteness.

Forward Connection: This result can also be viewed as minimizing the quadratic form $f(x, y) = [x^\top \ y^\top] M [x^\top \ y^\top]^\top$ with respect to $y$ (partial minimization), yielding a new quadratic form in $x$ defined by the Schur complement matrix. This perspective is explored in Lecture 05.

Application: This lemma turns the nonlinear constraint $\|Bx\|_2^2 \le c$ (equivalent to $x^\top B^\top B x \le c$) into an LMI: $$ \begin{bmatrix} I & Bx \\ (Bx)^\top & c \end{bmatrix} \succeq 0 $$ This is central to Semidefinite Programming.

A positive definite matrix $Q$ can be used to define a generalized norm, $\|x\|_Q = \sqrt{x^\top Q x}$. The unit ball for this norm, $\{x \mid x^\top Q x \le 1\}$, is an ellipsoid, whose geometry is determined by the eigenvalues and eigenvectors of $Q$.

6.6 The Loewner Order

For symmetric matrices $X, Y \in \mathbb{S}^n$, we write $X \succeq Y$ if and only if $X - Y$ is positive semidefinite (PSD), meaning:

The Loewner order is the language of:

• Ellipsoids (defined by PSD matrices in quadratic forms)
• PSD cone $\mathbb{S}^n_+ = \{X \in \mathbb{S}^n \mid X \succeq 0\}$ in Lecture 03
• Semidefinite programs (SDPs) in Lecture 08

7. Projections onto Subspaces and Affine Sets

The concept of "finding the closest point" is the geometric heart of optimization. Whether solving least squares, applying constraints, or analyzing duality, we are often just computing an orthogonal projection.

7.1 Projection onto a Line (1D Case)

Before tackling general subspaces, let's rigorously derive the projection of a vector $x$ onto the line spanned by a single non-zero vector $a \in \mathbb{R}^n$. This simple case contains all the intuition needed for the general theory.

We seek the scalar $\alpha$ that minimizes the squared distance $\|x - \alpha a\|_2^2$. $$ f(\alpha) = \|x - \alpha a\|_2^2 = (x - \alpha a)^\top (x - \alpha a) = \|x\|_2^2 - 2\alpha (a^\top x) + \alpha^2 \|a\|_2^2 $$ This is a simple convex quadratic in $\alpha$. Setting the derivative to zero: $$ f'(\alpha) = -2(a^\top x) + 2\alpha \|a\|_2^2 = 0 \implies \alpha^\star = \frac{a^\top x}{\|a\|_2^2} $$ The projection is the vector $p = \alpha^\star a$: $$ p = \frac{a^\top x}{a^\top a} a = \left( \frac{a a^\top}{a^\top a} \right) x $$

7.2 Orthogonal Projection onto a General Subspace

Let $\mathcal{S} \subseteq \mathbb{R}^m$ be a subspace and $b \in \mathbb{R}^m$. The orthogonal projection $p \in \mathcal{S}$ of $b$ is the unique vector in $\mathcal{S}$ minimizing $\|b - p\|_2$. It is characterized by the condition that the residual is orthogonal to the entire subspace: $$ b - p \perp \mathcal{S} \quad \iff \quad v^\top(b - p) = 0 \ \ \forall v \in \mathcal{S} $$

Projection via a Basis

If $Q \in \mathbb{R}^{m \times k}$ has orthonormal columns spanning $\mathcal{S}$, the projector is: $$ P = QQ^\top \quad \text{and} \quad p = Pb = QQ^\top b $$ Check: $P^2 = P$ (idempotent) and $P^\top = P$ (symmetric)—that's what makes it an orthogonal projector.

Projection onto $\mathcal{R}(A)$ using $A$

If $A \in \mathbb{R}^{m \times n}$ has full column rank: $$ P = A(A^\top A)^{-1} A^\top \quad \text{and} \quad p = Pb $$

Projection onto an Affine Set

Consider an affine set defined by $\mathcal{A} = \{ x \in \mathbb{R}^n \mid Fx = g \}$, where $F \in \mathbb{R}^{p \times n}$ has full row rank and $g \in \mathbb{R}^p$. Projecting onto this set reduces to subspace projection by translating. This concept is generalized in Lecture 01 to projection onto convex sets (POCS).

Explicit Formula via Least Norm

We solve the problem $\min \|x - y\|_2^2$ s.t. $Fx = g$. The KKT conditions yield the linear system: $$ \begin{bmatrix} I & F^\top \\ F & 0 \end{bmatrix} \begin{bmatrix} x \\ \nu \end{bmatrix} = \begin{bmatrix} y \\ g \end{bmatrix} $$ Solving for $x$ gives the explicit projection formula: $$ \Pi_{\mathcal{A}}(y) = y - F^\top (F F^\top)^{-1} (F y - g) $$ This is often more practical than constructing a nullspace basis $Z$.

Parametric Representation

Every point in $\mathcal{A}$ can be written as $x = x_0 + Zt$, where:

• $x_0$ is any particular solution satisfying $Fx_0 = g$.
• $Z$ is a matrix whose columns form a basis for $\mathcal{N}(F)$ (the nullspace of $F$).
• $t \in \mathbb{R}^k$ where $k = n - p$ (dimension of the nullspace).

Euclidean Projection Formula (Explicit via KKT)

Alternatively, using Lagrange multipliers (a technique we will explore deeply in Lecture 09), we can derive the projection without forming a nullspace basis.

Euclidean Projection Formula (Nullspace)

The Euclidean projection of any point $y \in \mathbb{R}^n$ onto $\mathcal{A}$ can also be computed via the nullspace basis:

8. The Method of Least Squares

The Problem: Overdetermined Systems

In practice, we often encounter linear systems $Ax=b$ with no exact solution. This typically occurs when $m > n$ (more equations than unknowns) and $b \notin \mathcal{R}(A)$. The "least squares" approach finds the best approximate solution by minimizing the sum of squared errors—the squared Euclidean norm of the residual $r = Ax-b$. This formulates the canonical unconstrained optimization problem:

Geometric Interpretation: Projection

The solution to the least squares problem has a clean geometric interpretation. The vector $Ax$ lies in the column space of $A$, denoted $\mathcal{R}(A)$. The problem $\min_x \|Ax - b\|_2$ is therefore equivalent to finding the point $p \in \mathcal{R}(A)$ that is closest to $b$ in Euclidean distance.

The 1D Case: Projection onto a Vector

Before solving the general case, consider projecting $x$ onto the line spanned by a vector $y \neq 0$. We want to find $t$ to minimize $\|x - ty\|_2^2$. $$ \phi(t) = \|x - ty\|_2^2 = \|x\|_2^2 - 2t(x^\top y) + t^2 \|y\|_2^2 $$ Taking the derivative with respect to $t$: $$ \phi'(t) = -2(x^\top y) + 2t \|y\|_2^2 $$ Setting $\phi'(t) = 0$ gives the optimal scaling: $$ t^\star = \frac{x^\top y}{\|y\|_2^2} $$ The projection is $p = t^\star y$.
Orthogonality Check: Let the residual be $r = x - p$. Then $y^\top r = y^\top x - t^\star y^\top y = y^\top x - \frac{x^\top y}{\|y\|^2} \|y\|^2 = 0$. The residual is orthogonal to $y$. This intuition generalizes to subspaces.

By the Pythagorean theorem, the closest point $p$ must satisfy a specific geometric condition: the error vector $b - p$ must be orthogonal to the subspace $\mathcal{R}(A)$. Think of dropping a perpendicular: The shortest path from a point to a plane (subspace) is the straight line perpendicular to that plane. If the error vector were not orthogonal, we could project it onto the subspace to find a "correction" that brings us closer to $b$, contradicting the optimality of $p$. Thus, the optimal $p = Ax^\star$ is the orthogonal projection of $b$ onto $\mathcal{R}(A)$.

The Normal Equations

The orthogonality condition, $(b - Ax^\star) \perp \mathcal{R}(A)$, implies that the residual vector must be orthogonal to every basis vector of the subspace. Since the columns of $A$ span $\mathcal{R}(A)$, the residual must be orthogonal to each column of $A$. This can be expressed compactly as: $$ A^\top (b - Ax^\star) = 0 $$ Expanding this yields the normal equations: $$ A^\top A x^\star = A^\top b $$ If the matrix $A$ has linearly independent columns (full column rank), then $A^\top A$ is invertible, and we can write the unique solution as $x^\star = (A^\top A)^{-1} A^\top b$.

Uniqueness of the Solution

• If $A$ has full column rank ($\mathrm{rank}(A) = n$), the solution $x^\star$ is unique.
• If $A$ is rank-deficient ($\mathrm{rank}(A) < n$), there are infinitely many solutions. In this case, the pseudoinverse is used to find the solution with the minimum norm.

8.4 Variants: Weighted and Constrained Least Squares

(a) Weighted Least Squares (WLS)

Given SPD weight $W \in \mathbb{R}^{m \times m}$: $$ \min_x \|Ax - b\|_W^2 := (Ax - b)^\top W(Ax - b) $$ Let $C$ be a matrix such that $W = C^\top C$ (e.g., via Cholesky decomposition). Then the problem is equivalent to ordinary least squares in the whitened system, minimizing $\|C(Ax - b)\|_2^2 = \|CAx - Cb\|_2^2$. The normal equations are $A^\top W A x = A^\top W b$.

(b) Constrained to an Affine Set

Solve: $$ \min_x \|Ax - b\|_2^2 \quad \text{s.t.} \quad Fx = g $$ One method: parametrize $x = x_0 + Zy$, where $Fx_0 = g$ and columns of $Z$ form a basis for $\mathcal{N}(F)$. Then minimize $\|A(x_0 + Zy) - b\|_2^2$ over $y$ (an unconstrained LS). QR on $AZ$ is typically best.

9. Review & Cheat Sheet

Definitions

Key Theorems

• Rank-Nullity: $\dim \mathcal{R}(A) + \dim \mathcal{N}(A) = n$ (for $A \in \mathbb{R}^{m \times n}$).
• Spectral Theorem: Real symmetric matrices have real eigenvalues and orthogonal eigenvectors.
• Schur Complement: $M \succeq 0 \iff D \succ 0$ and $A - BD^{-1}B^\top \succeq 0$.
• Fundamental Theorem of Linear Algebra: $\mathcal{R}(A) \perp \mathcal{N}(A^\top)$ and $\mathcal{R}(A^\top) \perp \mathcal{N}(A)$.

Standard Formulas

• Normal Equations: $A^\top A x = A^\top b$
• Projection onto Subspace: $P = A(A^\top A)^{-1}A^\top$ (if $A$ full rank)
• Cauchy-Schwarz: $|x^\top y| \le \|x\|_2 \|y\|_2$
• Gradient of Quadratic: $\nabla (x^\top A x) = (A+A^\top)x$

11. Exercises

P0.1 — Linear Independence

Determine whether the following sets of vectors are linearly independent. If dependent, exhibit a linear combination summing to zero.

1. $v_1 = (1, 2, 3)^\top, v_2 = (4, 5, 6)^\top, v_3 = (7, 8, 9)^\top$.
2. $v_1 = (1, 0, 0)^\top, v_2 = (1, 1, 0)^\top, v_3 = (1, 1, 1)^\top$.
3. The columns of an upper triangular matrix with non-zero diagonal entries.

P0.2 — The Rank-Nullity Theorem

Let $A$ be a $10 \times 15$ matrix.

1. What is the maximum possible rank of $A$?
2. If the rank of $A$ is 8, what is the dimension of the nullspace $\mathcal{N}(A)$?
3. If $A x = 0$ has only the solution $x=0$, is this possible? Explain.

P0.3 — Orthogonal Complements

Let $S$ be a subspace of $\mathbb{R}^n$. The orthogonal complement is $S^\perp = \{y \mid y^\top x = 0 \ \forall x \in S\}$.

1. Prove that $S^\perp$ is a subspace.
2. Prove that $S \cap S^\perp = \{0\}$.
3. If $S = \text{span}((1, 0, 0)^\top, (0, 1, 0)^\top)$, calculate $S^\perp$.

P0.4 — Norm Equivalence

In finite dimensions, all norms are equivalent. For $x \in \mathbb{R}^n$, prove the following inequalities:

1. $\|x\|_\infty \le \|x\|_2 \le \sqrt{n} \|x\|_\infty$
2. $\|x\|_2 \le \|x\|_1 \le \sqrt{n} \|x\|_2$

P0.5 — Frobenius Norm Submultiplicativity

We proved $\|AB\|_F \le \|A\|_F \|B\|_F$ in the lecture using Cauchy-Schwarz.
Re-derive this result by writing $\|X\|_F^2 = \mathrm{tr}(X^\top X)$ and using the property $\mathrm{tr}(M) = \sum \lambda_i(M)$ along with the fact that $\lambda_{\max}(A^\top A) \le \mathrm{tr}(A^\top A)$.

P0.6 — Spectral Norm Properties

Let $\|A\|_2$ denote the spectral norm (max singular value).

1. Show that $\|A\|_2 = 0$ if and only if $A=0$.
2. Show that $\|Q A\|_2 = \|A\|_2$ for any orthogonal matrix $Q$. (Orthogonal invariance).

P0.7 — Isometries

An isometry is a linear map $f(x) = Qx$ that preserves distances: $\|Qx - Qy\|_2 = \|x - y\|_2$ for all $x, y$.
Show that this condition implies $Q^\top Q = I$. Thus, isometries are represented by orthogonal matrices.

P0.8 — Weighted Inner Product

Let $A \in \mathbb{S}^n_{++}$ be a symmetric positive definite matrix.
(a) Prove that $\langle x, y \rangle_A = x^\top A y$ satisfies all axioms of an inner product.
(b) Write down the Cauchy-Schwarz inequality for this inner product.

P0.9 — Characterization of Projectors

A matrix $P$ is an orthogonal projector if and only if it is idempotent ($P^2=P$) and symmetric ($P^\top=P$).
(a) Prove that if $P$ is an orthogonal projector onto a subspace $S$, it satisfies these conditions.
(b) Prove the converse.

P0.10 — Projection onto a Line

Let $a = (1, 1, 1)^\top$. Find the projection of $b = (1, 0, 0)^\top$ onto the line spanned by $a$. Verify that the residual $b - p$ is orthogonal to $a$.

P0.11 — Projection onto a Hyperplane

Find the projection of the point $y = (3, 3)^\top$ onto the line (hyperplane in 2D) defined by $x_1 + x_2 = 2$.

P0.12 — Trace and Determinant

1. Show that $\mathrm{tr}(ABC) = \mathrm{tr}(BCA)$ but generally $\mathrm{tr}(ABC) \neq \mathrm{tr}(BAC)$. Construct a $2 \times 2$ counterexample.
2. Let $A \in \mathbb{R}^{n \times n}$ be skew-symmetric ($A^\top = -A$). Show that $x^\top A x = 0$ for all $x$.
3. Use the result from (b) to prove that if $n$ is odd, $\det(A) = 0$. (Hint: $\det(A^\top) = \det(-A)$).

P0.13 — Matrix Calculus Practice

Compute the gradient with respect to $X \in \mathbb{R}^{n \times n}$ for the following functions:

1. $f(X) = \mathrm{tr}(A X B)$, where $A, B$ are constant matrices.
2. $f(X) = \mathrm{tr}(X^\top X)$.
3. $f(X) = a^\top X b$, where $a, b$ are constant vectors.

P0.14 — Testing Positive Semidefiniteness

Determine whether the following matrices are PSD, PD, Indefinite, or Negative Definite/Semidefinite.

1. $A = \begin{bmatrix} 2 & -1 \\ -1 & 2 \end{bmatrix}$
2. $B = \begin{bmatrix} 1 & 2 \\ 2 & 1 \end{bmatrix}$
3. $C = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 3 \end{bmatrix}$

P0.15 — Schur Complement Application

Use the Schur Complement condition (assuming the top-left pivot is positive) to determine the range of $x$ for which the matrix $M(x)$ is Positive Semidefinite:

Verify your answer by computing the eigenvalues directly.

P0.16 — Loewner Order Transitivity

The Loewner order is defined as $X \succeq Y \iff X - Y \succeq 0$. Prove that this order is transitive: if $X \succeq Y$ and $Y \succeq Z$, then $X \succeq Z$. Use the variational definition of PSD matrices.

P0.17 — PSD Cone in 2D

Consider the space of $2 \times 2$ symmetric matrices, which has dimension 3.
Write down the explicit inequalities defining the PSD cone $S \succeq 0$ in terms of the matrix entries $x, y, z$ (where $S = \begin{bmatrix} x & y \\ y & z \end{bmatrix}$). Relate this to the trace and determinant conditions.

P0.18 — Hessian of a Cubic

Let $f: \mathbb{R}^2 \to \mathbb{R}$ be defined by $f(x) = x_1^3 + x_2^3 + 2x_1 x_2$.

1. Compute the gradient $\nabla f(x)$.
2. Compute the Hessian matrix $\nabla^2 f(x)$.
3. For which $x$ is the Hessian Positive Semidefinite? (This identifies the region where the function is locally convex).

P0.19 — Least Squares from Scratch

Consider the function $f(x) = \frac{1}{2} \|Ax - b\|_2^2$.

1. Expand the squared norm into terms involving $x^\top A^\top A x$, etc.
2. Compute the gradient $\nabla f(x)$ step-by-step.
3. Set the gradient to zero to derive the Normal Equations.
4. Show that if $\mathcal{N}(A) = \{0\}$, the Hessian is positive definite, ensuring a unique global minimum.

P0.20 — General Quadratic Minimization

Solve the unconstrained minimization problem for a general quadratic function: $$ \min_{x \in \mathbb{R}^n} f(x) := \frac{1}{2} x^\top H x + g^\top x + c $$ where $H \in \mathbb{S}_{++}^n$ (Positive Definite).

11. Readings & Resources

• Boyd & Vandenberghe, Convex Optimization:
  • Appendix A: Mathematical Background (Norms, Analysis, Functions)
  • Appendix C: Numerical Linear Algebra (Operations, Factorizations)
• Gilbert Strang, Introduction to Linear Algebra:
  • Chapter 2: Vector Spaces
  • Chapter 3: Orthogonality
  • Chapter 6: Eigenvalues and Eigenvectors
• Golub & Van Loan, Matrix Computations:
  • Chapter 2: Matrix Multiplication (for numerical aspects)
  • Chapter 5: Orthogonalization and Least Squares